1. Field of the Invention
The present invention relates to data transmission systems and more particularly to a method and apparatus for facilitating correction of data loss in such a system. The invention is suitable for use in any telecommunications network or transmission path that includes an end-to-end or node-to-node connection for communication of multiple data streams between a pair of devices.
By way of example, and without limitation, the invention will be described in the context of transmitting packet based real time voice or other media signals over a packet switched computer network, for use in internet-based telephony (e.g., voice over IP (VoIP)). However, the invention may also be suitably employed to transmit other types of signals and over other networks (such as local area (LAN), metropolitan area (MAN) or wide area (WAN) networks, and circuit switched networks, for example) or direct end-to-end connections, as well as with other transmission protocols.
2. Description of the Related Art
In a packet switched network, a message to be sent is divided into blocks, or data packets, of fixed or variable length. The packets are then sent individually over the network through multiple locations and then reassembled at a final location before being delivered to a user at a receiving end. To ensure proper transmission and re-assembly of the blocks of data at the receiving end, various control data, such as sequence and verification information, is typically appended to each packet in the form of a packet header. At the receiving end, the packets are then reassembled and transmitted to an end user in a format compatible with the user""s equipment.
To facilitate packet-based communication over interconnected networks that may include computers of various architectures and operating systems, the networks and computers typically operate according to an agreed set of packet switching protocols. A variety of such protocols are available, and these protocols range in degree of efficiency and reliability. Those skilled in the art are familiar, for instance, with the Transmission Control Protocol/Internet Protocol (TCP/IP) suite of protocols, which is used to manage transmission of packets throughout the Internet and other packet switched networks.
Each protocol in the TCP/IP suite is designed to establish communication between common layers on two machines, or hosts, in the network. The lowest layer in the Internet is the xe2x80x9cphysicalxe2x80x9d layer, which is concerned with ensuring that actual bits and bytes of information pass along physical links between nodes of the network. The next layer is the link layer, which ensures a reliable connection between nodes in the network. The next layer is the xe2x80x9cnetworkxe2x80x9d or xe2x80x9cIPxe2x80x9d layer, which is concerned with permitting hosts to inject packets of data into the network to be routed independently to a specified destination. The next layer in turn is the xe2x80x9ctransportxe2x80x9d layer, which is concerned with allowing peer entities on source and destination hosts to carry on a conversation. Generally speaking, the IP and transport layers of the Internet are not concerned with the physical arrangement of the network, such as whether source and destination machines are on the same sub-network or whether there are other sub-networks between them.
The transport layer of TCP/IP includes two end-to-end protocols, TCP (Transmission Control Protocol) and UDP (User Datagram Protocol). TCP is a reliable connection-oriented protocol, which includes intelligence necessary to confirm successful transmission between the sending and receiving ends in the network. UDP, in contrast, is an unreliable connectionless protocol, which facilitates sending and receiving of packets but does not include any intelligence to establish that a packet successfully reached its destination. In general, UDP is used by applications that do not want TCP""s sequencing or flow control and wish to provide their own.
According to the TCP/IP model, the TCP transport layer takes a data stream to be transmitted and breaks it up into independent connectionless segments or xe2x80x9cdatagrams.xe2x80x9d TCP adds to each of these packages a 20 byte header, which includes overhead information such as a source port number, a destination port number and a sequence number designed to allow the receiving end to properly reassemble the datagrams into the original message. The transport layer then xe2x80x9cpassesxe2x80x9d each of these packages to the IP layer.
The IP layer in turn adds another header to each package, providing additional overhead information, such as a source IP address and a destination IP address. The IP layer then transmits the resulting packages through the Internet, possibly fragmenting each package into pieces or as it goes. As the pieces of the package finally reach the destination machine, they are reassembled by the IP layer and passed to the transport layer. The transport layer then arranges the original datagrams in proper sequence in an effort to reconstruct the original data stream for use by the receiving process and ultimately by an end user.
For real time data or media signals (such as voice or video) to be transmitted over packet switched networks, the packets to be transmitted may be encapsulated by one or more additional header layers according to established higher level protocols. An example of one such higher level protocol is Real Time Protocol or RTP. RTP may provide each packet with an 12 byte header containing timestamps and sequence numbers. Included in this header may be a 7 bit payload type, which may define the type of payload in the underlying data packet. In practice, when the transmitting and receiving network ends establish communication of such signals, they will negotiate a mutually acceptable meaning for these RTP payload types. By way of example, the RTP payload type may indicate the type of voice or video codec (e.g., G.729, G.723.1, etc.) used to compress the underlying media signal, thereby facilitating proper decoding at the receiving end.
Packet switched networks such as the Internet thus serve to provide end-to-end (or node-to-node) communication between a pair of network devices or machines. These network devices may access or be connected to the Internet through any suitable configuration. In a usual arrangement, for instance, each device is connected via a communications link (such as the public switched telephone network (PSTN) or a LAN) to a server or gateway that provides access to the Internet. The gateway is typically owned and operated by an Internet service provider (ISP) and is known as a network access server (NAS) or remote access server (RAS). Of course, the gateway itself may also be considered a network device or machine, as it serves to communicate over the network with a machine (e.g., another gateway) at another end or node.
Network access servers are commercially available from 3Com Corporation and other telecommunications equipment manufacturers such as Ascend Communications, Livingston Enterprises, and Multitech. A representative NAS is the Total Control Enterprise Network Hub from 3Com Corporation, as described in the patent of Dale M. Walsh, et al., U.S. No. 5,597,595 (xe2x80x9cthe Walsh patentxe2x80x9d), which is fully incorporated herein by reference. This NAS has a telephone line interface that can be connected to a high-speed multiplexed digital telephone line, such as a T1 line or an ISDN line. The NAS further provides a plurality of digital modems to perform signal conversions (such as voice or video encoding) on the data from the telephone line channels and a bus network connecting the modems to a network interface card or module. Examples of such network interface cards are the NetServer(trademark) and EdgeServer(trademark) cards from 3Com Corporation. The network interface card in turn couples the NAS to a local or wide area network, such as the ISP backbone network or the Internet.
While packet switched networks have traditionally been used to carry non-realtime transmissions (such as e-mail messages or other data transfers), one of the promising new uses of these networks is to carry telephone conversations and other interactive communications. Known as xe2x80x9cIP telephonyxe2x80x9d in the context of IP networks, the goal of this new technology is to replace or enhance conventional circuit switched telephone networks with more versatile and universal packet switched communications.
FIG. 1 illustrates a basic IP telephony configuration. In this configuration, users at two or more telephone devices are set to engage in a conversation over an IP network. Each telephone device may take any of a variety of forms. For instance, without limitation, the device may be a conventional analog telephone or a personal computer (PC) equipped with a handset (or a microphone and speakers) to facilitate a conversation. Each telephone device is served by an IP telephony gateway (ITG), which is owned by an IP telephony service provider (ITSP) and provides connectivity to the network. In practice, users may subscribe to the service provided by an ITSP and may then place and receive calls over the IP network via a communications link to their respective gateways.
The communications link may take any suitable form. For instance, if the telephone device is a conventional telephone, the communications link may be the conventional PSTN, with a T1 span extending to the ITG. In that case, a subscriber may place a call to the ITG over the PSTN. As another example, if the telephone device is a PC on a LAN, the communications link may be the LAN extending to the ITG. In that case, a subscriber may contact the ITG via the existing network connection. Of course, other suitable communications links are known or will be developed as well.
The ITG may take the form of a network access server similar to those described above, modified to the extent necessary to facilitate telephone conversations over the network. For instance, while the modems in a conventional NAS modulate and demodulate signals to communicate with subscribers"" PC modems, the xe2x80x9cmodemsxe2x80x9d in an ITG may not need to modulate or demodulate signals. Instead, the modems may be configured to receive the telephone signals originating at subscriber telephone devices and to sample (if necessary), compress and packetize the signals for transmission over the network, and vice versa for signals coming from the network.
Like other network access servers, an ITG will typically receive and process a plurality of telephone conversation signals from subscriber devices and transmit these signals in parallel over the IP network to a destination gateway. At a given moment, for instance, the ITG may simultaneously receive a plurality of unrelated speech signals from a given communications link such as a T1 span, process those signals as necessary, and place a series of corresponding RTP packets onto the network in one or more outgoing packet streams for transmission to a destination gateway.
In this regard, two or more signals may be communicated xe2x80x9cconcurrentlyxe2x80x9d, xe2x80x9cin parallelxe2x80x9d or xe2x80x9csimultaneouslyxe2x80x9d with each other, for example, by conveying the signals as separate sequences of data or packets at once, and/or by interleaving (e.g., time division multiplexing) the data from the signals into a single sequence and conveying that single sequence, or by other such techniques. In other words, unless specified otherwise, use of these terms in this document does not necessarily mean xe2x80x9cliterally togetherxe2x80x9d or xe2x80x9cliterally at the same timexe2x80x9d (which could be impossible in some configurations) but may more reasonably be construed to mean approximately together or approximately at the same time. For instance, provided with three packet streams, A={A1, A2, A3 . . . }, B={B1, B2, B3 . . . } and C={C1, C2, C3 . . . }, representing three separate conversations, an ITG may simultaneously transmit these three streams over an IP network to a remote ITG as a single TDM stream S={A1, B1, C1, A2, B2, C2, A3, B3, C3 . . . }.
Ideally, all of the packets transmitted into a packet switched network by the ITG should arrive successfully at the designated remote gateway, for conversion as necessary and transmission to the destination device. Either the remote gateway or the destination device, as the case may be, should then receive the transmitted IP packets, extract the payload from the packets and reconstruct an ordered data stream or signal for receipt by an end user.
Unfortunately, however, deficiencies in the existing communication infrastructure have precluded the successful widespread transmission of real time media signals, such as digitized voice, audio and video, from end-to-end over packet switched networks. One of the principles reasons for this lack of success is a high rate of packet loss and delay.
The Internet, for example, suffers from a high rate of packet loss and resulting transmission delays. In particular, depending on conditions such as how congested the Internet is at any given time, loss of entire packets has been found to occur on the Internet at a rate of up to 25%, or up to one in every four packets. Typically, this packet loss occurs one packet at a time, which might or might not perceptibly distort a real-time audio signal, but may perceptibly distort a real-time video signal, and would certainly distort a pure data signal such as an e-mail message. Often, however, burst errors occur on the Internet and result in the loss of multiple sequential packets in a row. Unlike the sporadic loss of a single packet, if left uncorrected, these burst errors can and will substantially and perceptibly distort almost any transmitted signal.
The connection-oriented TCP protocol provides a mechanism for responding to packet loss in an IP network. According to TCP, when a segment arrives at its destination, the receiving TCP entity should send back to the sending entity a segment bearing an acknowledgement number equal to the next sequence number that it expects to receive. If the sending entity does not receive an acknowledgement within a specified time period, it will re-transmit the package of data.
Generally speaking, this acknowledgment and re-transmission system works well to correct for packet loss. However, the system can unfortunately delay the complete transmission of a data stream. For the transmission of packets representing pure data signals such as e-mail messages, transmission delay is not ideal, although it is of secondary concern compared to an unrecoverable loss of information. Real-time media signals, however, are by definition highly sensitive to delay and will appear jumpy, interrupted or otherwise distorted if parts of the signal do not flow continuously to the receiving end. Further, in the context of interactive real-time communications such as packet-switched telephony, delay is even more problematic, since participants to such communications expect the network connection to simulate immediate, in-person interaction, without delay.
Rather than employing (or invoking) an acknowledgement and retransmission system, less delay in packet loss correction can be achieved by transmitting a correction code of some sort concurrently with the payload data, thereby providing the receiving end with sufficient information to recover lost packets. Several error correction code mechanisms are available for this purpose. These mechanisms include, for instance, convolution coding, interleaving and block coding, all of which are well known to those skilled in the art. Of these mechanisms, perhaps the most common is block coding.
Block coding calls for mapping a frame of binary source data into a coded block of data that includes a set of redundant parity symbols. By conventional terminology, an xe2x80x9c(n,k)xe2x80x9d block coder typically converts a group of k payload units (such as bytes or bits) from a data stream into a larger group of n units by deriving p=nxe2x88x92k parity units or forward error correction (FEC) codes. Each parity unit is generated through a predetermined coding technique based on all or some subset of the k payload units.
The parity units may then be transmitted in-stream with the underlying payload units (e.g., interleaved with the payload, or after the payload, or appended to the payload). Alternatively or additionally, the parity units may be transmitted in a separate stream in parallel with the underlying payload stream. This latter technique is described, for instance, in J. Rosenberg, H. Schulzrinne, An RTP Payload Format for Generic Forward Error Correction, Internet Engineering Task Force, Internet Draft, July 1998, the entirety of which is hereby incorporated herein by reference.
Many forms of block coding are now known. One of the simplest forms of a block code, for instance, is a repetition code, in which the binary source data is repeated as a set of parity bits. One of the more popular but complex block codes is the Reed-Solomon (RS) class of codes over the 28 Galois field. These codes are optimal in their ability to correct erased bytes. For example, provided that 8 bytes are protected with 3 parity bytes (a total of 11 bytes), any three bytes can be lost, and the original 8 bytes may still be recovered.
Another example of block coding is to append or concatenate redundant parity information to existing data packets in the packet stream. For instance, as an offshoot of traditional repetition codes, the transmitting node may append to each data packet redundant copies of the preceding k number of data packets. In this way, the receiving end may readily recover a lost packet Di from one of the k subsequent packets Di+l . . . Di+k. As more preceding packets are concatenated with each current packet in the stream, the network can then tolerate a higher rate of packet loss.
Still another block coding technique is described in co-pending U.S. patent application Ser. No. 08/989,616, entitled xe2x80x9cA Forward Error Correction System for Packet Based Real Time Mediaxe2x80x9d and filed on Dec. 12, 1997, the entirety of which is hereby incorporated by reference. According to this technique, parity bits associated with current packets are piggy-backed onto future packets. In particular, as a sequence of payload blocks is being transmitted, every k payload blocks in the sequence are fed through a block coder to create p=nxe2x88x92k forward error correction (FEC) codes or parity packets, where pxe2x89xa6k. Each of these p parity packets may then be concatenated respectively with one of the next p data packets being transmitted. In turn, at the receiving end, if a packet is lost, the associated payload may be extracted from the parity blocks carried by the appropriate subsequent group of packets.
Yet another coding technique is described in U.S. patent application Ser. No. 08/989,483, also entitled xe2x80x9cA Forward Error Correction System for Packet Based Real Time Mediaxe2x80x9d and filed on Dec. 12, 1997, the entirety of which is also hereby incorporated by reference. According to this technique, a single parity block p may be derived as an XOR sum of the payload carried by the preceding k packets in the stream and then concatenated with the current packet for transmission. With this technique, regardless of the number of sequential packets to be recovered at the receiving end, the size of the forward error correction code remains of the same order as the payload itself.
While each of these forward error correction coding techniques has its advantages, the existing techniques still suffer from at least one inherent disadvantage: delay. In particular, since the parity information, p, is derived as some function of group of preceding payload information, k, the receiving end will usually not receive the parity information until it first receives all of the payload information. Therefore, in response to a loss of some payload information, the receiving end will need to wait until the necessary parity information arrives in order to recover the lost information.
Further, provided with a complex coding scheme in which a number of the k payload units (as well as the parity unit(s)) are required in order to recover from a loss of one or more of the k payload units, the receiving end will need to wait until all of those necessary payload units arrive as well. Thus, regardless of whether the parity units for a given stream are transmitted in-stream with the underlying payload or in a separate FEC stream, some additional delay will inherently occur in responding to packet loss.
As noted above, any such delay is problematic in the context of real time media transmissions and particularly so in the context of interactive network communications such as IP telephony. While one way to reduce this delay may be to use less complex FEC schemes (such as simple repetition codes), that solution is likely to be unacceptable as the quality of error correction may decrease and the bandwidth may increase.
In view of these deficiencies in the existing art, a need exists for an improved system of forward error correction coding.
The present invention provides a simple yet elegant mechanism for forward error correction coding, suitable for use where multiple data streams are simultaneously transmitted (e.g., in a time, frequency or code division multiplexed stream) over a data network or other end-to-end connection. The invention stems from the realization that existing FEC encoding schemes are carried out within each real time stream to be transmitted. This encoding process inherently causes delay from at least two perspectives.
First, the transmitting end cannot generate and transmit the required parity information (e.g., the p units in a block coder) until it first knows of the underlying payload information (e.g., the k units) that will go into the parity computation. Second, assuming that packets arrive at the receiving end in approximately the same order that they were transmitted, the receiving end will probably need to wait for both the parity information and the underlying payload information to arrive before it can recover lost payload. This is the case whether the FEC information is transmitted in-stream with the underlying payload and/or transmitted in a separate stream in parallel with the underlying payload stream. The basic problem is that the parity information is computed and/or transmitted after the underlying payload information.
The present invention advantageously introduces a new dimension to the FEC encoding process, which achieves a substantial reduction in the time delays that were inherent in the art. According to the invention, FEC encoding is conducted in parallel across multiple data streams that are to be transmitted concurrently from one location to another, rather than within the individual data streams. In one embodiment, for instance, the resulting parity information may then take the form of a parity data stream that may itself be transmitted to the remote location in parallel with the underlying payload data streams. As a consequence, the receiving end can receive all of the information necessary to recover from a data loss much sooner in time, if not immediately, after it detects the data loss.
Except to the extent claimed, the particular FEC coding scheme used is not pertinent to the present invention, except that the resulting parity information should preferably be transmitted to the receiving end closely in time (or concurrently) with the underlying payload information. As a result, the parity information can theoretically arrive at the receiving end together with (i.e., in parallel with) all of the underlying payload information, rather than after all of the underlying payload information. Consequently, the receiving end will, for all practical purposes, not have to wait for the underlying payload and parity information to arrive before correcting for data loss. The invention thus beneficially facilitates recovery from data loss without adding additional delay.
According to one embodiment, the present invention may include generating parallel FEC information based on a parallel combination of at least two data streams that are transmitted in parallel over a network from a first device to a second device (i.e., destined for receipt by the second device), and transmitting that parallel FEC information to the second device in parallel with the underlying data streams. In this embodiment, the first and second devices may be positioned at locations remote from each other, and the network may be a packet switched network and each of the data streams may be a packet stream representing an underlying independent telephone conversation.
Further, in this embodiment, the parallel FEC information may be derived as a functional combination of the data packets in the underlying packet streams, according to a predetermined FEC encoding scheme. The parallel FEC information may then take the form of a parity packet stream, which may be transmitted in parallel with the underlying packet streams, such as by time division multiplexing the parity packet stream with the underlying packet streams. Except for any packets lost in transmission, then, the second device should receive a given set of parity information at about the same time as it receives the underlying data information that was functionally combined to result in the parity information. In addition, for reference by the receiving end, each of the packets in the parity packet stream may be labeled as a parallel FEC packet by including an appropriate header, such as a predetermined RTP payload type.
Alternatively, as noted above, the present invention may extend to transmission over a circuit switched network or other type of network or direct end-to-end connection. Further, the payload that is transmitted over the network may represent any type of media or data signals, such as, for example, voice (e.g., telephone conversation signals), video (e.g., video conferencing signals), audio (e.g., radio signals), or pure data signals (e.g., e-mail signals).
By way of example, in the context of IP telephony, an embodiment of the invention may be carried out in a common processing unit in the ITG and may include deriving and transmitting a separate FEC packet stream based on a parallel combination of a plurality of independent conversation streams. For instance, assume that subscribers A and B are each served by the same local ITG and are concurrently engaging in separate IP telephony conversations with other subscribers served by a common remote ITG. According to one application of the invention, the local ITG may continuously derive a separate FEC packet stream whose data is computed as an XOR sum of packets in the unrelated conversation streams representing voices from A and B, respectively, and the local ITG may transmit that separate FEC packet stream to the remote ITG in parallel with the underlying conversation streams. Beneficially, (assuming that the packets arrive somewhat in sequence) the remote ITG can then receive all information necessary for recovery of a lost packet immediately (or almost immediately) when the remote ITG detects the packet loss.
The foregoing as well as other advantages of the present invention will become apparent to those of ordinary skill in the art by reading the following detailed description, with appropriate reference to the accompanying drawings.